import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-01-13
 * Time: 16:07
 */
public class Sort {

    // [以下所有排序均以升序排序为例]
    /**
     * 插入排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * 特点：排第 i个的时候说明前 i-1个已经有序了
     * @param array
     */
    public static void insertSort(int[] array) {
        // 从 1 下标开始，向前插入
        for (int i = 1; i < array.length; i++) {
            // 记录待插入下标 i 的值
            int tmp = array[i];
            // 将 i 下标对应值分别和 i 下标之前的元素比较
            int j = i - 1;
            for (; j >= 0; j--) {
                if (tmp < array[j]) {
                    // 升序排序：如果 value(i) 小于之前元素，该元素向后挪动
                    array[j + 1] = array[j];
                } else {
                    // 如果 value(i) > 前面的某一个元素值，即找到插入位置，跳出循环
                    break;
                }
            }
            // 代码走到这里表示：
            // 1.break跳出循环，即在[0,i]下标之间找到小于value(i)的元素
            // 2.value(i) 在 [0,i]下标之间是最小的
            array[j + 1] = tmp;
        }
    }


    /**
     * 希尔排序：插入排序的一种优化\
     * 时间复杂度：O(N^1.3-N^1.5)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     *
     * @param array
     */
    public static void shellSort(int[] array) {
        // 确定增量 gap
        int gap = array.length;
        while (gap > 1) {
            shell(array, gap);
            // 每次增量减少
            gap = gap / 2;
        }
        // 增量为1时再排一次
        shell(array, gap);

    }

    private static void shell(int[] array, int gap) {
        // 初始时 i = gap ，使下标 i 指向第 1 组的第 2 个元素
        // 便于对每一组执行插入排序
        for (int i = gap; i < array.length; i++) {
            // 记录待插入下标 i 的值
            int tmp = array[i];
            // 下标 j 指向每组的已排序序列
            int j = i - gap;
            // 寻找每组 value(i) 的插入位置
            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            // 代码走到这里表示：找到插入位置
            array[j + gap] = tmp;
        }

    }


    //下面经常用到交换，抽象出一个函数
    public static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }


    /**
     * 选择排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     *
     * @param array
     */
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            // 初始化最小值下标
            int minIndex = i;
            // 寻找待排元素中最小值
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    //更新最小值下标
                    minIndex = j;
                }
            }
            // 此时minIndex放的是最小元素的下标
            swap(array, minIndex, i);
        }
    }


    /**
     * 选择排序变种
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     *
     * @param array
     */
    public static void selectSort2(int[] array) {
        // 待排序列起始下标
        int left = 0;
        // 待排序列终止下标
        int right = array.length - 1;

        // 遍历待排序列
        while (left < right) {
            // 初识值，假定最小最大值下标都在最左边
            int maxIndex = left;
            int minIndex = left;
            //每次找到当前范围内的最大值下标：maxIndex；最小值下标：minIndex
            for (int i = left + 1; i <= right; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            // 确定最小值位置
            swap(array, left, minIndex);
            // 如果最大值对应待排序列的起始下标，需要特殊处理，
            // 因为上面的交换会将最大值换到下标 minIndex 处
            if (maxIndex == left) {
                maxIndex = minIndex;
            }
            // 确定最大值位置
            swap(array, right, maxIndex);

            // 缩小待排序列范围
            left++;
            right--;
        }
    }


    /**
     * 冒泡排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     *
     * @param array
     */
    public static void bubbleSort(int[] array) {
        // 外层循环控制比较的轮数
        for (int i = 0; i < array.length - 1; i++) {
            // 判断是否有序的标志
            boolean flag = true;
            // 内层循环进行相邻元素的比较和交换，每一轮次比较个数少1（优化1）
            for (int j = 0; j < array.length - 1 - i; j++) {
                // 这里是升序
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    // 只要进入比较就说明还不一定有序
                    flag = false;
                }
            }
            //如果在一趟比较中一次都不比较说明已经有序，不需要继续遍历（优化2）
            if (flag) {
                break;
            }
        }
    }

    /**
     * 堆排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     *         //升序：创建大根堆
     *         //降序：创建小根堆
     * @param array
     */
    public static void heapSort(int[] array) {
        // 将源序列构建为大根堆
        creatHeap(array);
        // 进行堆排序
        // 从后向前调整待排序列
        int end = array.length - 1;
        while (end > 0) {
            swap(array, 0, end);
            shiftDown(array, 0, end);
            end--;
        }

    }

    //这里是建立大根堆->升序排序
    private static void creatHeap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(array, parent, array.length);
        }
    }
    // 向下调整算法
    private static void shiftDown(int[] array, int parent, int len) {
        int child = 2 * parent + 1;
        //一定有左孩子
        while (child < len) {
            //有左孩子和右孩子
            if (child + 1 < len && array[child] < array[child + 1]) {
                child++;
            }
            // 此时child拿到最大值孩子下标
            if (array[child] > array[parent]) {
                swap(array, child, parent);

                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }


    /**
     * 快速排序
     * 时间复杂度：N*logN
     *         最好情况 ：N*logN(每次均匀分割待排序列)
     *         最坏情况：N^2  有序、逆序（根取基准值有关系）  优化！！！
     * 空间复杂度：
     *         最好情况：logN
     *         最坏情况：N
     * 稳定性：不稳定
     * @param array
     */
    //注：快速排序的阶段性排序结果的特点是：第i趟完成时，会有i个以上的数出现在它
    //最终将要出现的位置上，即它左边的数都比它小，他右边的数都比它大。
    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }
    private static void quick(int[] array,int start,int end) {
        //这里取大于等于，因为可能不同时存在大于和小于基准值的数值
        if (start>=end) {
            return;
        }
        // 优化二：递归到小的子区间时，可以考虑使用插入排序
        if (end-start+1<=16) {
            quickInsert(array,start,end);
            return;
        }
        // 优化一：三数取中法选 pivot ，防止单枝树
        int index = midThree(array,start,end);
        // 每次将 pivot 值换到 start 位置
        swap(array,start,index);

        int pivotIndex = partition2(array,start, end);//划分
        quick(array,start,pivotIndex-1);
        quick(array,pivotIndex+1,end);
    }

    /*优化*/
    // 1.三数取中法选 pivot，防止单枝树

    private static int midThree(int[] array,int left,int right) {
        int mid = (left+right)/2;

        if (array[left]<array[right]) {
            if (array[mid]>array[right]) {
                return right;
            } else if (array[mid]<array[left]) {
                return left;
            } else {
                return mid;
            }

        } else {
            //array[left]>=array[right]的情况
            if (array[mid]>array[left]) {
                return left;
            } else if (array[mid]<array[right]) {
                return right;
            } else {
                return mid;
            }
        }

    }
    // 2. 递归到小的子区间时，可以考虑使用插入排序[利用越有序越快的特点]
    public static void quickInsert(int[] array,int left,int right) {
        //这里从1开始，默认0下标（第一个元素）有序
        for (int i = left+1; i <=right; i++) {
            int tmp = array[i];//记录i下标的值
            //将i下标对应值分别和i下标后元素比较
            int j = i - 1;
            for (; j >= left; j--) {
                //升序排序：如果小于其后元素，向后挪动
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            //挪完之后，当找到array[j]<tmp时，或数组走完了，j==-1时
            array[j + 1] = tmp;
        }
    }



    // 将区间按照基准值划分为左右两半部分的常见方式有：
    // 1.Hoare版
    private static int partition(int[] array, int left, int right) {
        // 记录初始时pivot下标
        int i = left;
        // 记录基准值
        int pivot = array[left];
        while (left < right) {
            // 注意取等，否则可能会出现左右横跳的死循环！[left和right相等时]
            // 注意取左边为基准值就右边 right 先走
            // 1.寻找右边小于piovt的值
            while (left < right && array[right] >= pivot) {
                right--;
            }
            // 2.寻找左边大于pivot的值
            while (left < right && array[left] <= pivot) {
                left++;
            }
            // 交换
            swap(array, left, right);
        }
        // left == right 时，让下标值交换
        swap(array, left, i);
        // 此时 left 和 right 均指向pivot基准值，返回即可
        return left;
    }

    // 2.挖坑法
    private static int partition2(int[] array, int left, int right) {
        // 保存基准值
        int pivot = array[left];
        while (left < right) {
            //注意条件取等(原因同 hoare)
            // 1.寻找右边小于piovt的值
            while (left < right && array[right] >= pivot) {
                right--;
            }
            // 入坑
            array[left] = array[right];
            // 2.寻找左边大于piovt的值
            while (left < right && array[left] <= pivot) {
                left++;
            }
            // 入坑
            array[right] = array[left];
        }
        // pivot 值入坑
        array[left] = pivot;
        // 返回pivot值对应下标
        return left;
    }

    // 3.前后指针
    private static int partition3(int[] array,int left,int right) {
        // 初始化指针位置
        int prev= left;
        int cur = left+1;
        while(cur<= right) {
            // 条件限制，保证不相邻时 prev 下标记录的是左边小于基准值的最后一个
            if (array[cur]<array[left] && array[++prev]!=array[cur]) {
                swap(array,prev,cur);
            }
            cur++;
        }
        // 上面走完了需要把基准值放到 prev 下标下
        swap(array,prev,left);
        // 返回基准值下标
        return prev;
    }

    /**
     * 快速排序非递归[使用栈]
     * 时间复杂度：N*logN
     *         最好情况 ：N*logN
     *         最坏情况：N^2  有序、逆序  优化！！！
     * 空间复杂度：
     *         最好情况：logN
     *         最坏情况：N
     * 稳定性：不稳定
     * @param array
     */
    public static void quickSort2(int[] array) {
        // 创建栈
        Deque<Integer> stack = new LinkedList<>();
        // 进行第一次划分
        int left = 0;
        int right = array.length - 1;
        if (left < right) {
            stack.push(left);
            stack.push(right);
        } else {
            return;
        }
//        int pivotIndex = partition(array, left, right);
//        // 判断左子序列是否存在两个以上元素
//        if (pivotIndex > left + 1) {
//            stack.push(left);
//            stack.push(pivotIndex - 1);
//        }
//        // 判断右子序列是否存在两个以上元素
//        if (pivotIndex < right - 1) {
//            stack.push(pivotIndex + 1);
//            stack.push(right);
//        }
        // 循环出栈
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            // 对子序列进行划分
            int pivotIndex = partition(array,left,right);
            // 判断左子序列是否存在两个以上元素
            if (pivotIndex > left + 1) {
                stack.push(left);
                stack.push(pivotIndex - 1);
            }
            // 判断右子序列是否存在两个以上元素
            if (pivotIndex < right - 1) {
                stack.push(pivotIndex + 1);
                stack.push(right);
            }
        }
    }


    /**
     * 归并排序
     * 时间复杂度：N*logN->小于快排
     * 空间复杂度：O(N)
     * 稳定性：稳定
     * @param array
     */
    public static void mergeSort(int[] array) {
        // 为了接口的统一性，这里将归并排序抽象出一个方法
        mergeSortFunc(array,0,array.length-1);
    }
    // 归并排序
    private static void mergeSortFunc(int[] array, int start,int end){
        // 当元素个数小于等于 1 时，分解停止
        if (start >= end) {
            return;
        }
        // 递归分解
        int mid = (start+end)/2;
        // 左子序列[left,mid]
        mergeSortFunc(array,start,mid);
        // 右子序列[mid+1,right]
        mergeSortFunc(array,mid+1,end);
        // 合并排序
        merge(array,start,end,mid);

    }

    // 递归完成后的合并排序过程
    private static void merge(int[] array,int left,int right,int mid) {
        // 定义两个变量分别指向两个数组的头
        int s1 = left;
        int s2 = mid+1;

        // 定义一个临时数组用来存储“和并排序”的数据
        int[] tmp = new int[right-left+1];
        // 临时数组下标
        int k = 0;
        // 进行“合并排序”的条件是两个子数组均不越界
        while (s1<=mid && s2<=right) {
            if (array[s1]<array[s2]) {
                tmp[k++] = array[s1++];
            } else {
                tmp[k++] = array[s2++];
            }
        }
        // 将还没走完的数组全部排入临时数组中
        while (s1<=mid) {
            tmp[k++] = array[s1++];
        }
        while (s2<=right) {
            tmp[k++] = array[s2++];
        }

        // 将排好的数据放入原来的数组中->注意: i+left找到原数组对应下标
        for (int i = 0; i < tmp.length; i++) {
            array[i+left] = tmp[i];
        }
    }

    /**
     * 归并排序->非递归实现
     * 注：这种非递归的写法，相当于省去了递归的过程（废话）直接从每组一个元素的情况开始向上合并
     * 时间复杂度：N*logN
     * 空间复杂度：O(N)
     * 稳定性：稳定
     * @param array
     */
    public static void mergeSort2(int[] array) {
        // gap 表示当前每组多少个有序元素
        int gap = 1;

        // 合并过程
        // 因为每组最多为 array.length 个，所以 gap < array.length
        while (gap < array.length) {
            // 两组两组的合并序列
            // i += gap * 2 表示去合并另外两组有序序列
            for (int left = 0; left < array.length; left += gap * 2) {

                int mid = left+gap-1;
                // 有可能会越界，处理越界情况
                if(mid >= array.length) {
                    mid = array.length-1;
                }
                int right = mid+gap;
                // 有可能会越界，处理越界情况
                if(right>= array.length) {
                    right = array.length-1;
                }
                // 进行合并排序
                merge(array,left,right,mid);
            }
            // 当前为每2个一组有序，下次变成4个一组有序
            gap *= 2;
        }
    }


    /**
     * 计数排序
     * 时间复杂度： O(N+范围)
     * 空间复杂度：O(范围)
     * 稳定性：当前代码无法确定稳定性
     * @param array
     */
    public static void countSort(int[] array) {
        //1. 遍历数组 找到最大值 和 最小值
        int min =array[0];
        int max =array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i]<min) {
                min = array[i];
            }
            if (array[i]>max) {
                max = array[i];
            }
        }
        //2. 根据范围 确定计数数组的长度
        int len = max - min + 1;
        int[] count = new int[len];
        //3.遍历数组，在计数数组当中 统计每个元素出现的次数
        for (int i = 0; i < array.length; i++) {
            // 下标值 i - min 表示相对位置
            int index = array[i]-min;
            count[index]++;
        }

        int k=0;
        //4.遍历计数数组，根据元素的累加次数，将对应元素放入待排序列中
        for (int i = 0; i < count.length; i++) {
            while (count[i]!=0) {
                // 下标值 i + min 表示真实的数据
                array[k++] = i+min;
                count[i]--;
            }
        }
    }

    // 测试：2023_7_28_21:10
//    public static void main(String[] args) {
//        int[] arr = new int[100];
//        for (int i = 0; i < 100; i++) {
//            arr[i] = arr.length-i;
//        }
//        System.out.println(Arrays.toString(arr));
//        quickSort2(arr);
//        System.out.println(Arrays.toString(arr));
//
//    }


}





